package com.lry.basic.algorithm.recursion;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/12/27
 */


//给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
//        示例 1:
//        输入:
//        11110
//        11010
//        11000
//        00000
//        输出: 1
//
//        示例 2:
//        输入:
//        11000
//        11000
//        00100
//        00011
//        输出: 3


public class NumIslands {


    public int numIslands(char[][] grid) {
        if(null==grid||grid.length==0||grid[0].length==0)
            return 0;
        int num = 0;
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j]=='1'){
                    dfs(i,j,grid);
                    num++;
                }
            }
        }
        return num;
    }

    private void dfs(int i,int j,char[][]grid){
        grid[i][j] = '0';
        for(int x=-1;x<=1;x++){
            for(int y=-1;y<=1;y++){
                int nx = i+x;
                int ny = j+y;
                //如果斜方向可以的话 这个条件(i==nx||j==ny)不需要
                if(nx>=0&&nx<grid.length&&ny>=0&&ny<grid[0].length&&grid[nx][ny]=='1'&&(i==nx||j==ny)){
                    dfs(nx,ny,grid);
                }
            }
        }
    }
}
